/**
 * 复杂度的几种表达式
 *
 * 属于P问题，99%可以遇见
 * O(1) 常数级
 * O(log(n)) 指数级
 * O(n) 线性级
 * O(n^2) 指数级
 *
 *  属于NP问题,不常见
 * O(2^n) 级数级
 *
 *
 */

/**
 *
 * 有序数组的二分查找法时间复杂度是O(log(n))
 *
 * 使用递归函数 实现二分查找
 * 
 * 斐波那契数列
 * f(n) = f(n-1)+f(n-2)
 *
 */

function findIndexByOrderArrayOfFab(arr: number[], value: number, start?: number, end?: number): number {

    end = end || arr.length - 1;
    start = start || 0;
    // 递归函数首先要有终止条件
    if (start > end) return -1

    let center = Math.floor((start + end) / 2);
    if (arr[center] == value) {
        return center
    } else if (arr[center] > value) { //继续递归左边的数组
        return findIndexByOrderArrayOfFab(arr, value, start, center - 1);
    } else {
        return findIndexByOrderArrayOfFab(arr,value,center+1,end)
    }
}

let testArr = [1, 3, 4, 5, 6, 7, 8, 9, 34, 56, 78, 122];

console.log(findIndexByOrderArrayOfFab(testArr, 78));
